#include "clib_rbtree.h"
 
static inline void 
rb_link_node(struct rb_node *node, struct rb_node *parent,
				struct rb_node **rb_link)
{
	node->rb_parent = (unsigned long)parent;
	node->rb_left = node->rb_right = NULL;

	*rb_link = node;
}

static inline void
rb_rotate_left(rbtree_t *rbtree,rbnode_t* rbnode)
{
    rbnode_t *right  = rbnode->rb_right;
	rbnode_t *parent = rb_get_parent(rbnode);

	if ((rbnode->rb_right = right->rb_left)) {
        rb_set_parent(right->rb_left, rbnode);
    }
		
	right->rb_left = rbnode;

	rb_set_parent(right, parent);

	if (parent)
	{
		if (rbnode == parent->rb_left) {
            parent->rb_left = right;
        }	
		else {
            parent->rb_right = right;
        }		
	}
	else {
        rbtree->root = right;
    }
	
	rb_set_parent(rbnode, right);
}

static inline void
rb_rotate_right(rbtree_t *rbtree,rbnode_t* rbnode)
{
    rbnode_t *left = rbnode->rb_left;
	rbnode_t *parent = rb_get_parent(rbnode);

	if ((rbnode->rb_left = left->rb_right))
		rb_set_parent(left->rb_right, rbnode);
	left->rb_right = rbnode;

	rb_set_parent(left, parent);

	if (parent)
	{
		if (rbnode == parent->rb_right) {
            parent->rb_right = left;
        }
		else {
            parent->rb_left = left;
        }	
	}
	else {
        rbtree->root = left;
    }
	
	rb_set_parent(rbnode, left);
}

static inline void
rb_insert_color(rbtree_t *rbtree, rbnode_t *rbnode)
{
	rbnode_t *parent, *gparent;

	while ((parent = rb_get_parent(rbnode)) && rb_is_red(parent))
	{
		gparent = rb_get_parent(parent);

		if (parent == gparent->rb_left)
		{
			{
				register struct rb_node *uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					rbnode = gparent;
					continue;
				}
			}

			if (parent->rb_right == rbnode)
			{
				register struct rb_node *tmp;
				rb_rotate_left(rbtree, parent);
				tmp = parent;
				parent = rbnode;
				rbnode = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			rb_rotate_right(rbtree, gparent);
		} else {
			{
				register struct rb_node *uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					rbnode = gparent;
					continue;
				}
			}

			if (parent->rb_left == rbnode)
			{
				register struct rb_node *tmp;
				rb_rotate_right(rbtree, parent);
				tmp = parent;
				parent = rbnode;
				rbnode = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			rb_rotate_left(rbtree, gparent);
		}
	}

	rb_set_black(rbtree->root);
}

static inline void
rb_erase_color(rbtree_t *rbtree,rbnode_t *node, rbnode_t *parent)
{
	rbnode_t *that;

	while ((!node || rb_is_black(node)) && node != rbtree->root)
	{
		if (parent->rb_left == node) {
			that = parent->rb_right;
			if (rb_is_red(that)) {
				rb_set_black(that);
				rb_set_red(parent);
				rb_rotate_left(rbtree, parent);
				that = parent->rb_right;
			}
			if ((!that->rb_left || rb_is_black(that->rb_left)) &&
			    (!that->rb_right || rb_is_black(that->rb_right)))
			{
				rb_set_red(that);
				node = parent;
				parent = rb_get_parent(node);
			}
			else {
				if (!that->rb_right || rb_is_black(that->rb_right)) {
					rb_set_black(that->rb_left);
					rb_set_red(that);
					rb_rotate_right(rbtree, that);
					that = parent->rb_right;
				}
				//rb_set_color(that, rb_color(parent));
				//rb_set_parent(that,two)
				that->clocr = parent->clocr;
				rb_set_black(parent);
				rb_set_black(that->rb_right);
				rb_rotate_left(rbtree, parent);
				node = rbtree->root;
				break;
			}
		}
		else {
			that = parent->rb_left;
			if (rb_is_red(that)) {
				rb_set_black(that);
				rb_set_red(parent);
				rb_rotate_right(rbtree, parent);
				that = parent->rb_left;
			}
			if ((!that->rb_left || rb_is_black(that->rb_left)) &&
			    (!that->rb_right || rb_is_black(that->rb_right)))
			{
				rb_set_red(that);
				node = parent;
				parent = rb_get_parent(node);
			}
			else {
				if (!that->rb_left || rb_is_black(that->rb_left)) {
					rb_set_black(that->rb_right);
					rb_set_red(that);
					rb_rotate_left(rbtree, that);
					that = parent->rb_left;
				}
				//rb_set_color(that, rb_color(parent));
				that->clocr = parent->clocr;
				rb_set_black(parent);
				rb_set_black(that->rb_left);
				rb_rotate_right(rbtree, parent);
				node = rbtree->root;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}

int  rb_add(rbtree_t *rbtree,rbnode_t *rbnode,rbnode_cmp_fn less)
{
    int result;
	rbnode_t *node;
    rbnode_t *tmp ;
	tmp = node = rbtree->root;
    
	while (node) {
		tmp = node;
		result = less(rbnode, node);
		if (result < 0)
			node = node->rb_left;
		else if (result > 0)
			node = node->rb_right;
		else {
			return -1;
		}
	}

    rb_set_parent(rbnode,tmp);

	if (!tmp)
		rbtree->root = rbnode;
	else if (result < 0)
		tmp->rb_left = rbnode;
	else
		tmp->rb_right = rbnode;

    rb_insert_color(rbtree,rbnode);

	return 0;
}

int  rb_del(rbtree_t *rbtree,rbnode_t *rbnode)
{
    rbnode_t *child, *parent;
	int color;

	if (!rbnode->rb_left)
		child = rbnode->rb_right;
	else if (!rbnode->rb_right)
		child = rbnode->rb_left;
	else
	{
		rbnode_t *old = rbnode, *left;

		rbnode = rbnode->rb_right;
		while ((left = rbnode->rb_left) != NULL)
			rbnode = left;

		if (rb_get_parent(old)) {
			if ((rb_get_parent(old))->rb_left == old)
				(rb_get_parent(old))->rb_left = rbnode;
			else
				(rb_get_parent(old))->rb_right = rbnode;
		} else
			rbtree->root = rbnode;

		child = rbnode->rb_right;
		parent = rb_get_parent(rbnode);
		color = rb_color(rbnode);

		if (parent == old) {
			parent = rbnode;
		} else {
			if (child)
				rb_set_parent(child, parent);
			parent->rb_left = child;

			rbnode->rb_right = old->rb_right;
			rb_set_parent(old->rb_right, rbnode);
		}

        rbnode->clocr     = old->clocr;
        rbnode->rb_parent = old->rb_parent;
		rbnode->rb_left   = old->rb_left;
		rb_set_parent(old->rb_left, rbnode);

		goto color;
	}

	parent = rb_get_parent(rbnode);
	color = rb_color(rbnode);

	if (child)
		rb_set_parent(child, parent);
	if (parent)
	{
		if (parent->rb_left == rbnode)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		rbtree->root = child;

 color:
	if (color == rbnode_black)
		rb_erase_color(rbtree,child, parent);
    
    return 0;
}

rbnode_t *rb_find(rbtree_t *rbtree,void *key,rbtree_find_fn look_up) 
{
	int cmp;
	rbnode_t *node = rbtree->root;
	while(node) {
		cmp = look_up(node,key);
		if(cmp > 0) {
			node = node->rb_left;
		}
		else if (cmp < 0) {
			node = node->rb_right;
		}
		else {
			return node;
		}
	}
	return NULL;
}

rbnode_t *rb_first(rbtree_t *rbtree)
{
    rbnode_t * node = (rbnode_t *)rbtree->root;

    if (!node) return NULL;

    while (node->rb_left != NULL)
        node = node->rb_left;

    return node;
}

rbnode_t *rb_last (rbtree_t *rbtree)
{
    rbnode_t *node = (rbnode_t *)rbtree->root;

    if (!node) return NULL;
 
    while (node->rb_right != NULL) 
        node = node->rb_right;
 
    return node;
}

rbnode_t *rb_prev (rbnode_t *rbnode)
{
    rbnode_t *node = rbnode;
    rbnode_t *prev = NULL;

    if (!node)
        return NULL;
 
    /* 如果node存在左孩子，则其前驱结点为 "以其左孩子为根的子树的最大结点" */

    if (node->rb_left != NULL) {
		node = node->rb_left;
		
		while (node->rb_right)
			node=node->rb_right;
		
		return node;
	}
        

    /* 如果node没有左孩子。则有以下两种可能：
     * (1)node是一个右孩子，则其前驱结点为它的父结点
     * (2)node是一个左孩子，则查找node的最低的父结点，并且该父结点要具有右孩子，
     *    找到的这个"最低的父结点"就是"node的前驱结点 */

    prev = rb_get_parent(node);

    while (prev != NULL && node == prev->rb_left) {
        node = prev;
        prev = rb_get_parent(node);
    }
 
    return prev;
}

rbnode_t *rb_next (rbnode_t *rbnode)
{
    rbnode_t  *node = rbnode;
    rbnode_t  *next = NULL;
 
    if (!node) return NULL;
 
    /* 如果node存在右孩子，则其后继结点为 "以其右孩子为根的子树的最小结点" */

    if (node->rb_right != NULL) {
		node = node->rb_right;
		while(node->rb_left)
			node = node->rb_left;
		
		return node;
	}
	
    /* 如果node没有右孩子。则有以下两种可能：
     * (1)node是一个左孩子，则其后继结点为它的父结点
     * (2)node是一个右孩子，则查找node的最低的父结点，并且该父结点要具有左孩子，
     *    找到的这个"最低的父结点"就是"node的后继结点 */

    next = rb_get_parent(node);

    while (next != NULL && node == next->rb_right) {
        node = next;
        next = rb_get_parent(node);
    }
 
    return next;
}
